This invention relates generally to programming of digital computers, and, more specifically, to memory management and garbage collection.
There are presently two broad approaches to memory management: (1) programmer memory management where programmers are responsible for writing explicit program code to de-allocate memory for the storage of objects no longer needed by a program; and (2) automatic memory management where the de-allocation of memory is done automatically, after the system determines that objects are no longer needed.
If memory management is automatic, there is no room left for programmer errors in memory management, which result in memory leaks, dangling pointers, or both.
A memory leak occurs when a program fails to de-allocate an object which it no longer needs. The accumulation of such unneeded objects during the execution of a program can lead to an unnecessary exhaustion of memory available for executing the program, end a resultant program abortion.
A dangling pointer reflects the converse mistake in memory management. This occurs when program code is executed which de-allocates an object while pointers to it still exist in an executing program. If some portion of code attempts to use the de-allocated object through a pointer it still possesses, the result is unpredictable and usually erroneous.
Automatic memory management removes the possibility of either of these errors. There is therefore an increase in the expectation of the reliability of a program executed with automatic memory management, over one executed with programmer-controlled explicit memory management. There is a significant labor savings in developing software for a system that supplies automatic memory management, since memory management mistakes are difficult to discover. However, automatic memory management systems do exact a toll in the efficiency of the programs using them, as is discussed below.
Many garbage collection methods have been proposed, the purpose of all of which is to discover, automatically and in as little processing time as possible, what objects in a program's memory are no longer needed by a program, so that those objects can be de-allocated and their storage reclaimed. Some of these garbage collection methods have significant processing overhead, which reduces the desirability of these methods and even precludes them from being used in certain applications (such as high-speed real-time systems). Thus, it is desirable that automatic memory management be as efficient as possible, to allow the broadest range of applicability.
Many garbage collection systems are constructed so as to suspend the normal execution of a program at random intervals, in order to find and delete objects in memory that are no longer needed. A program executed with such a garbage collection system can never be depended on to run in exactly the same manner as any prior execution, even given all of the same operating conditions and inputs. Determinism is lost.
Determinism is important for real-time applications where physical processes outside a computer controlling them are occurring at a fixed rate. The software controlling such computers must be able to guarantee that it will respond to external events within known time limits. Under such circumstances, the use of a non-deterministic garbage collection mechanism may be precluded.
One approach to garbage collection uses reference counting. In this method, each object has a property attached to it called its reference count, which is merely the number of objects that possess a pointer to that object. Clearly, when an object's reference count becomes zero, it may safely be de-allocated.
It is fairly simple and somewhat efficient to manage a reference count for an object, but the method has a significant limitation involving circular references. Suppose a program allocates objects A and B, stores a reference to A in B, and stores a reference to B in A. Now, even if all other references to the objects A and B are deallocated, A and B would each have a reference count of 1, indicating their references to each other. Thus, A and B would never be de-allocated, and this represents a memory leak.